<?php
require $root . "/Map/BinarySearchTreeMap.php";

/**
 * 字典树
 * Class Trie
 */
class Trie
{
    private $root = null;
    private $size;

    public function __construct()
    {
        $this->root = new TrieNode();
    }

    /**
     * 向字典树中添加
     * @param string $word向字段树中添加元素
     */
    public function add(string $word, $value)
    {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $c = $word[$i];
            if ($node->next->get($c) == null) {
                $node->next->add($c, new TrieNode($value));
            }
            $node = $node->next->get($c);
        }

        if (!$node->isWord) {
            $node->isWord = true;
            $this->size++;
        }
    }

    /**
     * 查看单词 word 是否存在 Trie 树中
     * @param $word
     */
    public function contains($word)
    {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $c = $word[$i];
            if ($node->next->get($c) == null) {
                return false;
            }
            $node = $node->next->get($c);
        }

        if ($node->isWord) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 获取字段树节点信息
     * @param $word
     */
    public function get($word)
    {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $c = $word[$i];
            if ($node->next->get($c) == null) {
                return null;
            }
            $node = $node->next->get($c);
        }
        return $node->value;
    }

    /**
     * 判断某个字符串是否为单词前缀
     * @param string $prefix
     * @return bool
     */
    public function isPrefix(string $prefix)
    {
        $node = $this->root;
        for ($i = 0; $i < strlen($prefix); $i++) {
            $c = $prefix[$i];
            if ($node->next->get($c) == null) {
                return false;
            }
            $node = $node->next->get($c);
        }
        return true;
    }

    public function getSize()
    {
        return $this->size;
    }
}

class TrieNode
{
    public $isWord = false;
    public $next;
    public $value = null;

    public function __construct($value = null)
    {
        $this->value = $value;
        $this->next = new BinarySearchTreeMap();
    }
}